lib/Mi manual de algoritmos/version_maraton_suramericana_2008/src/dp/particion_troncos.cpp

   1 /*
   2   O(n^3)
   3
   4  dp[i][j] = Mínimo costo de partir la cadena entre las particiones i e j, ambas incluídas.
   5  */
   6 int dp[1005][1005];
   7 int p[1005];
   8
   9 int cubic(){
  10   int n, m;
  11   while (scanf("%d %d", &n, &m)==2){
  12     p[0] = 0;
  13     for (int i=1; i<=m; ++i){
  14       scanf("%d", &p[i]);
  15     }
  16     p[m+1] = n;
  17     m += 2;
  18
  19     for (int i=0; i<m; ++i){
  20       dp[i][i+1] = 0;
  21     }
  22
  23     for (int i=m-2; i>=0; --i){
  24       for (int j=i+2; j<m; ++j){
  25         dp[i][j] = p[j]-p[i];
  26         int t = INT_MAX;
  27         for (int k=i+1; k<j; ++k){
  28           t = min(t, dp[i][k] + dp[k][j]);
  29         }
  30         dp[i][j] += t;
  31       }
  32     }
  33
  34     printf("%d\n", dp[0][m-1]);
  35   }
  36   return 0;
  37 }
  38
  39
  40 /*
  41   O(n^2)
  42
  43   dp[i][j] = Mínimo costo de partir la cadena entre las particiones i e j, ambas incluídas.
  44   pivot[i][j] = Índice de la partición que usé para lograr dp[i][j].
  45  */
  46 int dp[1005][1005], pivot[1005][1005];
  47 int p[1005];
  48
  49 int quadratic(){
  50   int n, m;
  51   while (scanf("%d %d", &n, &m)==2){
  52     p[0] = 0;
  53     for (int i=1; i<=m; ++i){
  54       scanf("%d", &p[i]);
  55     }
  56     p[m+1] = n;
  57     m += 2;
  58
  59     for (int i=0; i<m-1; ++i){
  60       dp[i][i+1] = 0;
  61     }
  62     for (int i=0; i<m-2; ++i){
  63       dp[i][i+2] = p[i+2] - p[i];
  64       pivot[i][i+2] = i+1;
  65     }
  66
  67     for (int d=3; d<m; ++d){ //d = longitud
  68       for (int j, i=0; (j = i + d) < m; ++i){
  69         dp[i][j] = p[j] - p[i];
  70         int t = INT_MAX, s;
  71         for (int k=pivot[i][j-1]; k<=pivot[i+1][j]; ++k){
  72           int x = dp[i][k] + dp[k][j];
  73           if (x < t) t = x, s = k;
  74         }
  75         dp[i][j] += t, pivot[i][j] = s;
  76       }
  77     }
  78
  79     printf("%d\n", dp[0][m-1]);
  80   }
  81   return 0;
  82 }